package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class numTrees_ {
  public static void main(String[] args) {
    System.out.println(numTrees(3));
  }

  // 1. dp[i]表示由i个节点组成的二叉搜索树有dp[i]种
  // 2. 递推公式:
  // 头节点为1 = 左子树0节点 * 右子树2节点
  // 头节点为2 = 左子树1节点 * 右子树1节点
  // 头节点为3 = 左子树2节点 * 右子树0节点
  // dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]
  // dp[i] = dp[0] * dp[i - 1] + dp[1] * dp[i- 1 - 1] + ... + dp[i - 1] * dp[0]
  // 3. 初始化: dp[0] = 1, dp[1] = 1, dp[2] = 2
  // 4. 遍历顺序
  public static int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2 ; i <= n ; i++){
      for (int j = 0 ; j < i ; j++){
        dp[i] += dp[j] * dp[i - j - 1];
      }
    }
    return dp[n];
  }
}
